package a13_Tree.BSTree;

import java.util.NoSuchElementException;

/**
 * @Author quan
 * @Description 基于整型的二分搜索树
 * @Date 2023/4/3 19:37
 */
public class MyBST {
    private TreeNode root;//根节点
    private int size;//有效节点个数
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }
        public TreeNode(int val) {
            this.val = val;
        }
    }
    /**
     * 增：插入新节点一定保存在叶子节点：不断和根节点比较大小，若新的值小于根节点，则放在左子树的插入；否则在右子树的插入。直到碰到空节点为止。
     */
    //外部调用
    public void add(int val){
        //内部维护一个addProx函数
        root = addProx(root,val);
    }
    private TreeNode addProx(TreeNode root, int val) {
        //树为空
        if(root == null){
            //将新传入的val构建为一个新的节点
            TreeNode node = new TreeNode(val);
            size++;
            return node;//返回新的树的根节点
        } else if (val < root.val) {//在左子树插入
            root.left = addProx(root.left,val);
            return root;
        }
        root.right = addProx(root.right,val);
        return root;
    }
    /**
     * 查：查找最大最小和任意值。 最大值：不断向BST右侧遍历，碰到的第一个root.right为空的情况，则该根节点的值为最大值；最小值：左，第一个root.left==null
     * 任意值的查询就是二分查找。若走到空树还没找到特定值，则说明该值在BST中不存在。
     * */
    public int searchMax(){
        if(root == null){
            throw new NoSuchElementException("no element");
        }
        TreeNode maxNode = findMax(root);
        return maxNode.val;
    }
    private TreeNode findMax(TreeNode root) {
        if(root.right == null){
            return root;
        }
        return findMax(root.right);
    }
    //查找最小值
    public int searchMin(){
        if(root == null){
            throw new NoSuchElementException("no element");
        }
        TreeNode minNode = findMin(root);
        return minNode.val;
    }

    private TreeNode findMin(TreeNode root) {
        if(root.left == null){
            return root;
        }
        return findMin(root.left);
    }
    //查找任意值
    public boolean searchNum(int val){
        if(root == null){
            throw new NoSuchElementException("root is null,no such element!");
        }else{
            return searchNum(root,val);
        }
    }
    //内部定义searchNum函数
    private boolean searchNum(TreeNode root, int val) {
        if(val == root.val){
            return true;
        } else if (val < root.val) {
            searchNum(root.left,val);
            return true;
        } else {
            searchNum(root.right,val);
            return true;
        }
    }

    /**
     * 判断SBT中是否包含某个值
     */
    public boolean contains(int val){
        boolean result = containsProx(root,val);
        return result;
    }
    private boolean containsProx(TreeNode root, int val) {
        if(root == null){
            return false;
        }
        if(root.val == val){
            return true;
        } else if (root.val > val) {
            return containsProx(root.left,val);
        }
        return containsProx(root.right,val);
    }
    /**
     * 删除：最大值,最小值
     */ 
    public int removeMax(){
        TreeNode maxNode = findMax(root);
        root = removeMax(root);
        return maxNode.val;
    }
    //内部删除最大值函数
    private TreeNode removeMax(TreeNode root) {
        if(root.right == null){
            //当前的root节点就是最大值
            TreeNode left = root.left;
            root.left = root = null;
            size--;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }
    public int removeMin(){
        TreeNode node = findMin(root);//找到最小值的节点
        root = removeMin(root);
        return node.val;

    }
    //内部删除最小值函数
    private TreeNode removeMin(TreeNode root) {
        if(root.left == null){//root就是要被删除的节点
            TreeNode right = root.right;//先保存该节点的右孩子
            root.right = root = null;//清除该节点
            return right;//返回该右孩子
        }
        root.left = removeMin(root.left);//递归调用
        return root;
    }
    /**
     * 删除任意值:在当前以root为根的BST中删除值为val的节点，返回删除后的树根节点
     */
    public void remove(int val) {
        remove(root,val);
    }
    public TreeNode remove(TreeNode root, int val){
        //base case
        if(root == null){
            return null;
        } else if (val < root.val) {
            //在左子树的删除操作：递归调用
            root.left = remove(root.left,val);
            return root;
        } else if (val > root.val) {
            //在右子树的删除：递归调用
            root.right = remove(root.right,val);
            return root;
        } else{
            //当前节点就是要被删除的节点
            //(1)当该节点只有左孩子，没有右孩子->相当于最大值的删除
            if(root.right == null){
                TreeNode left = root.left;
                root.left = root = null;
                size --;
                return left;
            }
            //(2)当该节点只有右孩子，没有左孩子->相当于最小值的删除
            if(root.left == null){
                TreeNode right = root.right;
                root.right = root = null;
                size --;
                return right;
            }
            //(3)当前节点左右孩子都有，此时删除该节点，则需要一个新的节点顶替过来：
            //后来发现：该节点要么是该删除节点的左子树的最大值，要么是该删除节点的右子树的最小值
            TreeNode successor = findMin(root.right);//找到该顶替的节点：右子树的最小值
            successor.right = removeMin(root.right);//断开successor节点的右子树分支
            successor.left = root.left;
            root.left = root.right = root = null;//清空该根节点以及所有的子树分支
            return successor;//successor就是新的树根
        }
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        printBST(root,0,sb);
        return sb.toString();
    }
    /**
     * 在以当前root为根的BST中，将当前节点的层次和值，拼接到sb对象中
     */
    private void printBST(TreeNode root, int level, StringBuilder sb) {
        //base case
        if(root == null){
            sb.append(printLine(level));
            sb.append("Null\n");//树为空，直接打印Null
            return;
        }
        //当前树不为空
        sb.append(printLine(level));//先根据层数拼接--的个数
        sb.append(root.val);//拼接值
        sb.append("\n");//换行
        //递归的打印左树
        printBST(root.left,level+1,sb);
        //递归的打印右树
        printBST(root.right,level+1,sb);
    }

    private String printLine(int level) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < level; i++) {
            sb.append("--");//一层打印一次--
        }
        return sb.toString();
    }
}
